package now_coder.dp.solutions;

public class NCSolution154 {

    /*
     * 最长回文子序列
     *
     * 子序列问题的求解一般分为以下两种情况：
     *
     * 1.dp 数组为一维的情况（求最长上升子序列）：
     * dp 数组为一维，并且 dp[i] 表示 array[i] 为结尾的数组中最长上升子序列的最大长度
     *
     * 2.dp 数组为二维的情况（最长回文子序列/最长公共子序列），又分为以下两种：
     *      2.1 涉及到两个字符串或数组时，在子数组 arr1[0...i] 和 arr2[0...j] 中，我们要求的子序列（最长公共子序列）的长度为 dp[i][j]
     *      2.2 涉及到一个字符串或者数组时，在子数组 arr[i...j] 中，我们要求的序列（最长回文序列的值）为 dp[i][j]
     *
     * 那么状态转移方程就很简单了，如果确定了 dp[i][j] 之后：
     * 1.如果 arr[i] == arr[j]，那么 dp[i][j] = dp[i+1][j-1] + 2
     * 2.如果 arr[i] != arr[j]，那么 arr[i] 和 arr[j] 就不可能出现在 arr[i...j] 的最长回文子序列中，所以 dp[i][j] = max(dp[i+1][j], dp[i-1][j])
     */

}
